#include <algorithm>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
using namespace std;

/*
 *这个就是对数器的模板代码，可以用来测试题目
 * */

// 正确算法（暴力解法）
int ReversePair2(std::vector<int> &nums) {
  int res = 0;
  for (int i = 0; i < nums.size(); ++i) {
    for (int j = i + 1; j < nums.size(); ++j) {
      if (nums[i] > (2 * nums[j])) {
        ++res;
      }
    }
  }
  return res;
}

int merge(std::vector<int> &nums, int left, int mid, int right,
          std::vector<int> &tmps) {
  cout << "left :" << left << " mid " << mid << " right" << right << endl;
  int res = 0;
  int tmpleft = left;
  int tmpright = mid + 1;
  for (; tmpleft <= mid; ++tmpleft) {
    while ((tmpright <= right) &&
           ((2 * (long long)nums[tmpright]) < (long long)nums[tmpleft])) {
      ++tmpright;
    }
    res += tmpright - mid - 1;
  }

  cout << "retu " << res << endl;
  ;
  tmpleft = left;
  tmpright = mid + 1;
  int index = left;
  while ((tmpleft <= mid) && (tmpright <= right)) {
    if (nums[tmpleft] <= nums[tmpright]) {
      tmps[index] = nums[tmpleft];
      ++tmpleft;
    } else {
      tmps[index] = nums[tmpright];
      ++tmpright;
    }
    ++index;
  }
  while (tmpleft <= mid) {
    tmps[index] = nums[tmpleft];
    ++tmpleft;
    ++index;
  }
  while (tmpright <= right) {
    tmps[index] = nums[tmpright];
    ++tmpright;
    ++index;
  }
  for (int i = left; i <= right; ++i) {
    nums[i] = tmps[i];
    cout << nums[i] << " ";
  }
  cout << endl;
  return res;
}

int proc(std::vector<int> &nums, int left, int right, std::vector<int> &tmps) {
  if (left >= right) {
    return 0;
  }
  int mid = left + ((right - left) >> 1);
  int ress = proc(nums, left, mid, tmps) + proc(nums, mid + 1, right, tmps) +
             merge(nums, left, mid, right, tmps);
  return ress;
}
// 待测试算法（Kadane算法）
int ReversePair(vector<int> &nums) {
  std::vector<int> tmps;
  tmps.resize(nums.size());
  return proc(nums, 0, nums.size() - 1, tmps);
}
// 随机数组生成器
vector<int> generateRandomArray(int max_size, int min_val, int max_val) {
  int size = rand() % max_size + 1; // 保证至少1个元素
  vector<int> arr(size);
  for (int i = 0; i < size; ++i) {
    arr[i] = rand() % (max_val - min_val + 1) + min_val;
  }
  return arr;
}

int main() {
  srand(time(0)); // 设置随机种子
  const int TEST_TIMES = 100;
  const int MAX_SIZE = 5;
  const int MIN_VAL = -100;
  const int MAX_VAL = 100;

  for (int i = 0; i < TEST_TIMES; ++i) {
    vector<int> arr = {-5,
                       -5}; // generateRandomArray(MAX_SIZE, MIN_VAL, MAX_VAL);
    vector<int> a = arr;
    vector<int> b = arr;
    int a1 = ReversePair(a);
    int a2 = ReversePair2(b);
    if (a1 != a2) {
      cout << "err: " << a1 << " " << a2 << endl;
      for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
      }
      cout << endl;
      return 1;
    }
  }

  cout << "所有 " << TEST_TIMES << " 次测试通过！" << endl;
  return 0;
}
